package datastructure.linked.leetcode203;

/**
 * @Description: 算法实现类
 * @author: Yang Qiang
 * @create: 2021-11-16 22:32
 */
public class Solution {
    /**
     * 使用常规方式删除链表中指定元素
     * @param head: 头结点
     * @param val: 删除的值
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        // 如果当前节点不为null(从头节点开始), 并且当前节点就是需要删除的节点
        // 然后如果头结点的下一个节点还是不为null,并且是需要删除的节点, 就一直删
        // 直到删到不是待删除的节点
        while (head != null && head.val == val){
            // 得到需要删除的节点
            ListNode delNode = head;
            // 把需要删除的下一个节点赋值给当齐前节点, 以为你当前节点要被删除了
            head = head.next;
            // 然后把需要删除的下一个指针为null, 让垃圾回收
            delNode.next = null;
        }

        // 如果头节点为null, 就直接返回了
        if (head == null){
            return head;
        }

        // 如果待删除节点是中间节点
        ListNode prev = head;
        while (prev.next != null){// 头节点的下个节点不为null
            if (prev.next.val == val){// 头节点的下一个节点就是需要删除的节点
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                // 开始验证下一个节点
                prev = prev.next;
            }
        }
        return head;
    }



    /**
     * 使用递归方式删除链表中指定元素
     * @param head: 头结点
     * @param val: 删除的值
     * @return
     */
    public ListNode removeElements1(ListNode head, int val) {
        if (head == null){
            return head;
        }
        // 从最后一个元素往前一个个的删除, 也就是递归
        ListNode resNode = removeElements1(head.next, val);
        /*
         * 比如最后一个节点是待删除的节点, 那么就会返回最后一个节点的下一个节点也就是null
         * 然后把null节点拼接到最后一个节点的上一个节点的下一个节点了, 这样就把最后一个节点给删除了
         *
         * 然后递归的这样操作
         */
        if (head.val == val){
            return resNode;// 待删除元素是子链的头节点
        }else {
            head.next = resNode;
            return head;
        }
    }
}